package com.ztom.v2;

/**
 * @author ZhangTao
 */
public class Code95EditDistance {

    public int minDistance(String word1, String word2) {
        char[] str1 = word1.toCharArray();
        char[] str2 = word2.toCharArray();
        int m = str1.length;
        int n = str2.length;
//        return process(str1, str2, m, n);
        int[][] dp = new int[m + 1][n + 1];
        dp[0][0] = 0;
        // count1 = 0
        for (int c = 1; c <= n; c++) {
            dp[0][c] = c;
        }
        // count2 = 0
        for (int r = 1; r <= m; r++) {
            dp[r][0] = r;
        }
        for (int r = 1; r <= m; r++) {
            for (int c = 1; c <= n; c++) {
                if (str1[r - 1] == str2[c - 1]) {
                    dp[r][c] = dp[r - 1][c - 1];
                } else {
                    dp[r][c] = Math.min(Math.min(dp[r - 1][c] + 1, dp[r][c - 1] + 1), dp[r - 1][c - 1] + 1);
                }
            }
        }

        return dp[m][n];
    }

    public int process(char[] str1, char[] str2, int count1, int count2) {
        if (count1 == 0 && count2 == 0) {
            // 都处理成空串了, 无需再操作
            return 0;
        }
        if (count1 == 0) {
            // 需要增加 count2 个字符
            return count2;
        }
        if (count2 == 0) {
            // 需要删除 count1 个字符
            return count1;
        }
        if (str1[count1 - 1] == str2[count2 - 1]) {
            // 无需处理
            return process(str1, str2, count1 - 1, count2 - 1);
        }
        // 需要增删改
        int n1 = process(str1, str2, count1, count2 - 1) + 1;
        int n2 = process(str1, str2, count1 - 1, count2) + 1;
        int n3 = process(str1, str2, count1 - 1, count2 - 1) + 1;
        return Math.min(Math.min(n1, n2), n3);
    }
}
